Devices for and methods of computing modular multiplication take two forms, serial and interleaved. In the serial method, the final product is determined before the modulo reduction is performed. In the interleaved method, a modulo reduction is performed after each partial product is generated. The serial method has proved to be difficult to implement. Serial-method devices that operate at speeds required by the public typically exceed the size constraint placed upon them. Serial-method devices that are within the size constraint typically do not meet the desired speed requirement.
In the highly competitive field of modular multiplication many scholars are seeking and proposing devices for and methods of performing modular multiplication that they consider to be the fastest. One of the most promising methods has been offered by C. K. Koc and C. Y. Hung in a paper entitled "Carry-Save Adders for Computing the Product AB Modulo N," published in Electronics Letters, Vol. 26, No. 13, 21 June 1990, pp. 899-900. In this paper Koc and Hung suggest an interleaved method that yields a modular multiplication of n-bit numbers in n steps. Their method is based on scanning the multiplier one bit at a time, modulo reducing the partial products, and performing a sign estimation on each partial product.
In the first cycle of the method proposed by Koc and Hung, the value of one bit of the multiplier is determined. If the bit is a one, the multiplicand is added to the partial product which initially is zero. If the bit is zero, zero is added to the partial product. The partial product is then modulo reduced by subtracting 2.times.modulus from the partial product. If the result is estimated to be negative, the result is discarded. If the result is estimated to be positive the result replaces the partial product. Next, the modulus is subtracted from the partial product. Once again, if the result is estimated to be negative, the result is discarded. If the result is estimated to be positive the result becomes the partial product. The cycle continues until all of the bits in the multiplier have been scanned. The partial product remains in redundant form until all of the bits of the multiplier have been used. The final partial product is then converted to non-redundant form via a carry-look-ahead adder. The modulus is subtracted from the final partial product one last time. If the result is positive, the result is returned as AB modulo N. If the result is negative, the final partial product is returned as AB modulo N.
The present invention is an improvement upon the Koc and Hung method. Where Koc and Hung achieve modular multiplication in n steps, the present invention achieves modular multiplication in n/2 steps. The present invention accomplishes this feat by doing a two-bit scan of the multiplier and performing an additional subtraction in order to modulo reduce larger partial products.
C. H. N. Forster, S. S. Dlay, and R. N. Gorgui-Naguib took the work of Koc and Hung one step further in their paper entitled, "Carry Delayed Save Adders for Computing the Product A.B Modulo N in log.sub.2 N Steps," published in Electronics Letters, Vol. 26, No. 18, 30 August 1990. In this paper, Forster et. al. did not change the method proposed by Koc and Hung and did not recognize the improvement to the Koc and Hung method that the present inventor does. Forester et. al. only propose circuit changes that allow the method of Koc and Hung to run in parallel in order to improve performance.
Naofumi Takagi proposes the use of a two-bit scan of the multiplier in a paper entitled, "A Radix-4 Modular Multiplication Hardware Algorithm for Modular Exponentiation," published in IEEE Transactions On Computers, Vol. 41, No. 8, August 1992. But the method disclosed in this paper requires the use of a non-standard redundant number system which complicates the design of a modular multiplier. The present invention does not require this non-standard redundant number system.
U.S. Pat. Nos. 5,073,870 and 5,144,574, both entitled "Modular Multiplication Method and the System for Processing Data," disclose a modular multiplier that requires the transformation of the multiplicand to a non-standard form similar to the non-standard form proposed by Takagi above. The present invention does not require such a transformation.
The present invention improves upon the above identified devices and methods by disclosing a device and method which scans two bits of a multiplier per iteration, utilizes standard data representations, and requires one more addition per cycle in order to improve performance over the method of Koc and Hung by 100%.